7/19/2022 Aaron Seidlitz, Illinois CS
Illinois CS professor Sheldon Jacobson and PhD student Ian Ludden pair with collaborators from Industrial & Enterprise Systems Engineering to present algorithmic attempts at offsetting the effect of gerrymandering.
Written by Aaron Seidlitz, Illinois CS
Every 10 years, in response to new data from the census, the United States undergoes a process called political redistricting – the drawing of new electoral district boundaries based on this new census data.
What, on its face, could be a mathematical and scientific process has been upended through politization since the term “gerrymandering” first came into use in 1812. This term specifically references “the manipulation of district boundaries for political advantage.”
Still, algorithmic approaches have been ongoing since the 1960s, as Illinois Computer Science PhD student Ian Ludden points out in his recent paper co-written with CS professor Sheldon Jacobson, as well as PhD student, Rahul Swamy, and professor Douglas M. King from Industrial & Enterprise Systems Engineering.
The group worked on a new algorithmic approach of their own in the paper, entitled “A Bisection Protocol for Political Redistricting.”
Their work was conducted in parallel with a paper that Swamy led, along with co-authors Jacobson and King entitled “Multi-Objective Optimization for Politically Fair Districting: A Scalable Multilevel Approach,” which was recently accepted with Operations Research.
“I think that two principles really guided our work: humility and transparency,” Ludden said. “The transparency comes simply from making it clear what is going into our algorithms and what the processes are that we took to get our results. Our work is humble, in the sense that we did not approach this with a preconceived thought dictating our perception of what fairness means.
“Instead, we turned to political scientists and looked at what they’ve been studying for decades. Our goal was to incorporate their insights.”
The authors go on to define their bisection protocol as “a two-player zero-sum extensive-form game motivated by political redistricting in which two players alternately divide pieces of a region in half (up to rounding) to obtain a district plan.”
The authors believe that the bisection protocol applies ideas from fair division, especially fair cake-cutting, to political redistricting. They also compared this process to other fair division-inspired protocols, primarily the “I-cut-you-freeze” method.
Additionally, they found that when political geography is enforced, optimal strategies depend on the spatial voter distribution, as evidenced by experiments on small grids. Finally, they found that optimal bisection strategies in real-world instances are intractable, but a heuristic strategy using mixed-integer programming formulations shows how bisection might play out in states with 4 to 8 congressional districts.
Ultimately, their bisection protocol, according to Ludden, tends to produce nearly proportional seat-shares when both parties use optimal strategies in a simplified setting that ignores the state’s political geography, allowing geographical rearrangement of voters.
Despite the politicization of the issue, Ludden does see a way forward for methods like this to gain traction in the redistricting process.
“One practical direction our bisection protocol can be implemented is through an independent redistricting commission, or a small bipartisan redistricting commission,” Ludden said. “Even if fair division inspired protocol ideas like this aren’t officially adopted as the protocol for a particular state, at least with these commissions – which are becoming a bit more frequent in some areas, with a couple of representatives from each side of the aisle – this can be a great way to test out a different protocol to see what type of map can be produced.”
As the director of the Institute for Computational Redistricting, Jacobson has long investigated this matter.
“The work we do is always focused on trying to solve public policy problems to make the world a better place,” Jacobson said. “We use the amazing technical expertise and knowledge of fellow faculty members at the University of Illinois Urbana-Champaign, along with the remarkable creativity of our students, to achieve our goals.
“Ultimately, when you look at national policies and state policies, policy makers want evidence as a reason for change – and we try to provide that evidence.”
The paper that Swamy led presents “Mixed Integer Linear Programming (MILP) models for districting with political fairness criteria based on fundamental fairness principles such as vote-seat proportionality (efficiency gap), partisan (a) symmetry, and competitiveness.”
By creating an algorithm for mathematically fair district plans according to a variety of fairness metrics such as the efficiency gap, partisan asymmetry, and competitiveness, the group found that algorithmically-generated district plans cater to multiple stakeholders such as the voters and the political parties.
The data, code, and district plans are publicly available to promote algorithmic transparency.
“I think a key takeaway is that this is an evolving landscape,” Swamy said. “Even our understanding of what fairness means has evolved as a society over many decades. Meanwhile, we also see that technologies are getting better and better every year. What used to be hard problems to solve are a lot easier now.
“Still, there are still a lot of problems now that are challenging – like large input sizes – which causes algorithms to be iterated over time and for technologies to be improved as we push forward.”